package 回溯;

public class Queen2 {
	
	private int[] queen;
	private boolean[] cols;
	private boolean[] leftTop;
	private boolean[] rightTop;
	private int ways;
	
	public static void main(String[] args) {
		new Queen2().placeNQueen(8);
	}
	
	public void placeNQueen(int n) {
		if (n < 1) return;
		queen = new int[n];
		cols = new boolean[n];
		leftTop = new boolean[(n << 1) - 1];
		rightTop = new boolean[(n << 1) - 1];
		place(0);
	}
	
	public void place(int row) {
		if (row == cols.length) {
			ways++;
			show();System.out.println(ways);
			return;
		}
		
		for (int col = 0; col < cols.length; col++) {
			if (cols[col]) continue;
			if (leftTop[row - col + cols.length - 1]) continue;
			if (rightTop[row + col]) continue;
			
			queen[row] = col;
			cols[col] = true;
			leftTop[row - col + cols.length - 1] = true;
			rightTop[row + col] = true;
			place(row + 1);
			cols[col] = false;
			leftTop[row - col + cols.length - 1] = false;
			rightTop[row + col] = false;
		}
	}
	
	public void show() {
		for (int i = 0; i < queen.length; i++) {
			for (int j = 0; j < queen.length; j++) {
				if (queen[i] == j) {
					System.out.print("1 ");
				} else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
	}
}
